package com.mine;

public class MergeSort {
  public static void sort(int[] array) {
    merge(array, 0, array.length - 1);
  }

  private static void merge(int[] array, int start, int end) {
    // 出口条件
    if (start >= end) {
      return;
    }
    // 递归
    int middle = (start + end) / 2;
    merge(array, start, middle);
    merge(array, middle + 1, end);
    // 归并
    int[] tmp = new int[end - start + 1];
    int index = 0;
    int leftIndex = start;
    int rightIndex = middle + 1;
    while (leftIndex <= middle && rightIndex <= end) {
      if (array[leftIndex] < array[rightIndex]) {
        // 左边的合适
        tmp[index++] = array[leftIndex++];
      } else {
        // 右边的合适
        tmp[index++] = array[rightIndex++];
      }
    }
    // 把剩下的数字续上
    while (leftIndex <= middle) {
      tmp[index++] = array[leftIndex++];
    }
    while (rightIndex <= end) {
      tmp[index++] = array[rightIndex++];
    }
    for (int i = 0; i < tmp.length; i++) {
      array[start + i] = tmp[i];
    }
  }
}
